package com.zfl;

import java.util.ArrayList;

public class SearchInsert {

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.indexOf(1);
    }

    /**
     * @param nums
     * @param target 目标值
     * @return 目标值索引 或 目标值插入的位置
     */

    private int binarySearch(int[] nums, int target) {

        int left = 0, right = nums.length;
        int result = -1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                //找第一个
                result = mid;
                right = mid;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return result;
    }


    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;

        int left = 0, right = row * col;

        while (left < right) {
            int mid = left + (right - left) / 2;
            int i = mid / col;
            int j = mid - i * col;
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return false;
    }
}

